//
// Created by jiangpenghui on 2023/4/19.
//

#include "sort_algorithm.h"
#include <array>

void insert_sort(int *a, int n) {
    for (int j = 1; j < n; j++) {
        int key = a[j]; //待排序第一个元素
        int i = j - 1;  //代表已经排过序的元素最后一个索引数
        // 在已排序区循环比较，找到插入位置i
        while (i >= 0 && key > a[i]) {
            // 移动相邻元素
            a[i + 1] = a[i];
            i--;
        }
        // 插入位置
        a[i + 1] = key;
    }
}

/**
 *
 * @param arr 排序子数组
 * @param low 排序子数组第一个元素
 * @param mid 排序子数组最后一个元素
 * @param hig
 */
void merge(int *arr, int low, int mid, int high) {
    // 临时数组用于记录【low,high】排序结果
    int *result = new int[high - low + 1];

    // i 左边数组初始下标， j 右边数组初始下标  k哨兵下标（记入result区段中最值）
    int i = low, j = mid + 1, k = low;

    // 两个数组排序
    while (i <= mid && j <= high) {
        // 左，右数组进行合并排序（其中左，右数组已排序）
        // 双下标递增比较
        if (arr[i] <= arr[j]) {
            // result[k] = arr[i]; k++; i++
            result[k++] = arr[i++];
        } else {
            // result[k] = arr[j]; k++; i++
            result[k++] = arr[j++];
        }
    }

    // 情况1：左数组【i,mid】元素比【mid+1,j】多，转存左数组剩余元素到resutl
    while (i <= mid) {
        result[k++] = arr[i++];
    }
    // 情况2：右数组【mid+1,j】元素比【i,mid】多，转存右数组剩余元素到resutl
    while (j <= high) {
        result[k++] = arr[j++];
    }
    // 转存result已排好序数组
    for (int i = low; i < high; ++i)
        arr[i] = result[i];
    delete[] result;
}

// 归并排序
/**
 *
 * @param arr :排序数组
 * @param start ：排序开始范围
 * @param end ：排序结束范围
 */
void merge_sort(int *arr, int start, int end) {
    if (start >= end) return;
    int mid = (start + end) / 2;
    // 左右递归拆分元素
    merge_sort(arr, start, mid);
    merge_sort(arr, mid + 1, end);

    // 递归结束后回溯，对[start,mid]，[mid+1,low] 进行排序合并
    // 保证[start,end]范围元素已排序
    merge(arr, start, mid, end);
}

